/**
 分治法
 * @param {string} expression
 * @return {number[]}
 */
export var diffWaysToCompute = function (expression) {
  let memo = new Map()
  function dfs(exp) {
    if (memo.has(exp)) return memo.get(exp)
    let res = []
    for (let i = 0; i < exp.length; i++) {
      if (exp[i] === '+' || exp[i] === '-' || exp[i] === '*') {
        const lefts = dfs(exp.slice(0, i))
        const rights = dfs(exp.slice(i + 1))
        for (let left of lefts) {
          for (let right of rights) {
            res.push(compute(left, right, exp[i]))
          }
        }
      }
    }
    if (res.length === 0) res = [parseInt(exp)]
    memo.set(exp, res)
    return res
  }
  return dfs(expression)
}

function compute(left, right, operator) {
  if (operator === '+') return left + right
  if (operator === '-') return left - right
  if (operator === '*') return left * right
}
